题目链接 · 灵神原题解（署名来源）

答疑

问：需要几个哨兵节点？

答：一个就够了。一开始哨兵节点 $\mathit{\text{dummy}}$ 的 $\mathit{\text{prev}}$ 和 $\mathit{\text{next}}$ 都指向 $\mathit{\text{dummy}}$。随着节点的插入，$\mathit{\text{dummy}}$ 的 $\mathit{\text{next}}$ 指向链表的第一个节点（最上面的书），$\mathit{\text{prev}}$ 指向链表的最后一个节点（最下面的书）。

问：为什么节点要把 $\mathit{\text{key}}$ 也存下来？

答：在删除链表末尾节点时，也要删除哈希表中的记录，这需要知道末尾节点的 $\mathit{\text{key}}$。

阅读建议

先看写法二，理解核心思路；再看写法一，理解链表细节。

写法一：手写双向链表

Python 解法1

class Node:
    # 提高访问属性的速度，并节省内存
    __slots__ = 'prev', 'next', 'key', 'value'

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dummy = Node()  # 哨兵节点
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy
        self.key_to_node = {}

    # 获取 key 对应的节点，同时把该节点移到链表头部
    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.key_to_node:  # 没有这本书
            return None
        node = self.key_to_node[key]  # 有这本书
        self.remove(node)  # 把这本书抽出来
        self.push_front(node)  # 放到最上面
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        if node:  # 有这本书
            node.value = value  # 更新 value
            return
        self.key_to_node[key] = node = Node(key, value)  # 新书
        self.push_front(node)  # 放到最上面
        if len(self.key_to_node) > self.capacity:  # 书太多了
            back_node = self.dummy.prev
            del self.key_to_node[back_node.key]
            self.remove(back_node)  # 去掉最后一本书

    # 删除一个节点（抽出一本书）
    def remove(self, x: Node) -> None:
        x.prev.next = x.next
        x.next.prev = x.prev

    # 在链表头添加一个节点（把一本书放到最上面）
    def push_front(self, x: Node) -> None:
        x.prev = self.dummy
        x.next = self.dummy.next
        x.prev.next = x
        x.next.prev = x

C++ 解法1

// C++ 版待补充

C++ 解法2

struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;

    Node(int k = 0, int v = 0) : key(k), value(v) {}
};

class LRUCache {
private:
    int capacity;
    Node* dummy; // 哨兵节点
    unordered_map<int, Node*> key_to_node;

    // 删除一个节点（抽出一本书）
    void remove(Node* x) {
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    // 在链表头添加一个节点（把一本书放到最上面）
    void push_front(Node* x) {
        x->prev = dummy;
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }

    // 获取 key 对应的节点，同时把该节点移到链表头部
    Node* get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) { // 没有这本书
            return nullptr;
        }
        Node* node = it->second; // 有这本书
        remove(node); // 把这本书抽出来
        push_front(node); // 放到最上面
        return node;
    }

public:
    LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {
        dummy->prev = dummy;
        dummy->next = dummy;
    }

    int get(int key) {
        Node* node = get_node(key); // get_node 会把对应节点移到链表头部
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        Node* node = get_node(key); // get_node 会把对应节点移到链表头部
        if (node) { // 有这本书
            node->value = value; // 更新 value
            return;
        }
        key_to_node[key] = node = new Node(key, value); // 新书
        push_front(node); // 放到最上面
        if (key_to_node.size() > capacity) { // 书太多了
            Node* back_node = dummy->prev;
            key_to_node.erase(back_node->key);
            remove(back_node); // 去掉最后一本书
            delete back_node; // 释放内存
        }
    }
};

写法二：标准库

Python 解法3

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        # from collections import OrderedDict
        # OrderedDict = dict + 双向链表
        self.cache = OrderedDict()  # key -> value

    def get(self, key: int) -> int:
        if key not in self.cache:  # 没有这本书
            return -1
        # 有这本书，把这本书抽出来，放到最上面（last=False 表示移到链表头）
        self.cache.move_to_end(key, last=False)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        self.cache[key] = value  # 添加 key value 或者更新 value
        # 把这本书抽出来，放到最上面（last=False 表示移到链表头）
        self.cache.move_to_end(key, last=False)
        if len(self.cache) > self.capacity:  # 书太多了
            self.cache.popitem()  # 去掉最后一本书

C++ 解法3

// C++ 版待补充

C++ 解法4

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache_list; // pair 里面保存的是 key 和 value
    unordered_map<int, list<pair<int, int>>::iterator> key_to_iter; // key -> 链表节点迭代器

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto umap_iter = key_to_iter.find(key);
        if (umap_iter == key_to_iter.end()) { // 没有这本书
            return -1;
        }
        auto list_iter = umap_iter->second; // 有这本书
        // 把这本书（list_iter）从书堆（cache_list）中抽出来，放到最上面（cache_list.begin()）
        cache_list.splice(cache_list.begin(), cache_list, list_iter);
        return list_iter->second; // 返回这本书的 value
    }

    void put(int key, int value) {
        auto umap_iter = key_to_iter.find(key);
        if (umap_iter != key_to_iter.end()) { // 有这本书
            auto list_iter = umap_iter->second;
            list_iter->second = value; // 更新 value
            // 把这本书（list_iter）从书堆（cache_list）中抽出来，放到最上面（cache_list.begin()）
            cache_list.splice(cache_list.begin(), cache_list, list_iter);
            return;
        }
        // 新书，放到最上面（emplace_front）
        cache_list.emplace_front(key, value);
        key_to_iter[key] = cache_list.begin();
        // 书太多了
        if (key_to_iter.size() > capacity) {
            // 去掉最后一本书
            key_to_iter.erase(cache_list.back().first);
            cache_list.pop_back();
        }
    }
};

复杂度分析

• 时间复杂度：所有操作均为 $\mathcal{O}(1)$。
• 空间复杂度：$\mathcal{O}(min(p,\mathit{\text{capacity}}))$，其中 $p$ 为 $\text{put}$ 的调用次数。

思考题

在本题的基础上，为 $\mathit{\text{key}}$ 添加过期时间（$\mathtt{\text{put}}$ 调用时额外传入过期时间）。如果 $\mathit{\text{key}}$ 过期，则需要删除掉。

相似题目

• 460. LFU 缓存，图解 LFU

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府